class LRUCache {
    struct listnode
    {
        int key, value;
        listnode* prev;
        listnode* next;
        listnode(int k = 0, int v = 0) 
            : key(k), value(v), prev(nullptr), next(nullptr)
        {}
    };
public:
    LRUCache(int capacity) 
        : _capacity(capacity), _size(0)
    {
        _head = new listnode;
        _tail = new listnode;
        _head->next = _tail;
        _tail->prev = _head;
    }
    // 引入头尾两个虚拟节点，方便头插和尾删，头尾指针不用修改指向
    int get(int key) 
    {
        if (!_cache.count(key))
        {
            return -1;
        }
        else
        {
            listnode* node = _cache[key];
            move2head(node);
            return node->value;
        }
    }
    
    void put(int key, int value) 
    {
        if (!_cache.count(key))
        {
            listnode* newnode = new listnode(key, value);
            _cache[key] = newnode;
            _size++;
            add2head(newnode);
            if (_size > _capacity)
            {
                removetail();
            }
        }
        else
        {
            listnode* node = _cache[key];
            node->value = value;
            move2head(node);
        }
    }

    void add2head(listnode* node)
    {
        node->next = _head->next;
        _head->next->prev = node;
        _head->next = node;
        node->prev = _head;
    }

    void move2head(listnode* node)
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
        add2head(node);
    }

    void removetail()
    {
        listnode* tail = _tail->prev;
        tail->prev->next = tail->next;
        tail->next->prev = tail->prev;
        _cache.erase(tail->key);
        delete tail;
        _size--;
    }    
private:
    int _size;
    int _capacity;
    listnode* _head;
    listnode* _tail;
    unordered_map<int, listnode*> _cache;
};
